{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Lexicographically Smallest String After Substring Operation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #执行子串操作后的字典序最小字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个仅由小写英文字母组成的字符串 <code>s</code> 。在一步操作中，你可以完成以下行为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择&nbsp;<code>s</code> 的任一非空子字符串，可能是整个字符串，接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如，'b' 用 'a' 替换，'a' 用 'z' 替换。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回执行上述操作 <strong>恰好一次</strong> 后可以获得的 <strong>字典序最小</strong> 的字符串。</p>\n",
    "\n",
    "<p><strong>子字符串</strong> 是字符串中的一个连续字符序列。</p>\n",
    "现有长度相同的两个字符串 <code>x</code> 和 字符串 <code>y</code> ，在满足&nbsp;<code>x[i] != y[i]</code> 的第一个位置 <code>i</code> 上，如果&nbsp; <code>x[i]</code> 在字母表中先于 <code>y[i]</code> 出现，则认为字符串 <code>x</code> 比字符串 <code>y</code> <strong>字典序更小</strong> 。\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"cbabc\"\n",
    "<strong>输出：</strong>\"baabc\"\n",
    "<strong>解释：</strong>我们选择从下标 0 开始、到下标 1 结束的子字符串执行操作。 \n",
    "可以证明最终得到的字符串是字典序最小的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"acbbc\"\n",
    "<strong>输出：</strong>\"abaab\"\n",
    "<strong>解释：</strong>我们选择从下标 1 开始、到下标 4 结束的子字符串执行操作。\n",
    "可以证明最终得到的字符串是字典序最小的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"leetcode\"\n",
    "<strong>输出：</strong>\"kddsbncd\"\n",
    "<strong>解释：</strong>我们选择整个字符串执行操作。\n",
    "可以证明最终得到的字符串是字典序最小的。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 3 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [lexicographically-smallest-string-after-substring-operation](https://leetcode.cn/problems/lexicographically-smallest-string-after-substring-operation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [lexicographically-smallest-string-after-substring-operation](https://leetcode.cn/problems/lexicographically-smallest-string-after-substring-operation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"cbabc\"', '\"acbbc\"', '\"leetcode\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        #找字符串s中非a的第一个位置为开始，a之前的一个位置为结束\n",
    "        i,left,right,n = 0,-1,-1,len(s)\n",
    "        ans = \"\"\n",
    "        flag = False\n",
    "        while i<n:\n",
    "            if s[i]!='a' and not flag:\n",
    "                left = i\n",
    "                flag = True\n",
    "            if s[i]=='a' and flag:\n",
    "                right = i\n",
    "                break\n",
    "            i+=1\n",
    "        if i==n:\n",
    "            right = i\n",
    "        #表示没有找到替换的起点，也就说s中全是a，那么需要替换最后一个a保证字典序最小\n",
    "        if left==-1:\n",
    "            return s[:n-1]+\"z\"\n",
    "        for idx,c in enumerate(s):\n",
    "            if idx<left or idx>=right:\n",
    "                ans += c\n",
    "            else:\n",
    "                if c!='a':\n",
    "                    ans += chr(ord(c)-1)\n",
    "                else:\n",
    "                    ans += 'z'\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        #找字符串s中非a的第一个位置为开始，a之前的一个位置为结束\n",
    "        i,left,right,n = 0,-1,-1,len(s)\n",
    "        ans = \"\"\n",
    "        flag = False\n",
    "        while i<n:\n",
    "            #flag用于标记是否已经找到了起点\n",
    "            if s[i]!='a' and not flag:\n",
    "                left = i\n",
    "                flag = True\n",
    "            #当找到起点后，遇到的'a'的下标就是我们替换区间终点的位置\n",
    "            if s[i]=='a' and flag:\n",
    "                right = i\n",
    "                break\n",
    "            i+=1\n",
    "        #如果s遍历结束都没有找到终点，说明s中不存在a那么s的末尾就是我们要替换区间的终点\n",
    "        if i==n:\n",
    "            right = i\n",
    "\n",
    "        #left=-1表示没有找到替换的起点，也就说s中全是a，那么需要替换最后一个a保证字典序最小\n",
    "        if left==-1:\n",
    "            return s[:n-1]+\"z\"\n",
    "        #否则我们就从left到right依次替换区间内的字符\n",
    "        for idx,c in enumerate(s):\n",
    "            if idx<left or idx>=right:\n",
    "                ans += c\n",
    "            else:\n",
    "                if c!='a':\n",
    "                    ans += chr(ord(c)-1)\n",
    "                else:\n",
    "                    ans += 'z'\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        begin = 0\n",
    "        while(s[begin] == \"a\"):\n",
    "            begin += 1\n",
    "            if begin == len(s):\n",
    "                break\n",
    "        \n",
    "        end = begin\n",
    "        if end < len(s):\n",
    "            while(s[end] != \"a\"):\n",
    "                end += 1\n",
    "                if end == len(s):\n",
    "                    break\n",
    "        \n",
    "        if begin == end:\n",
    "            begin -= 1\n",
    "        p = \"\"\n",
    "        for i in range(0, begin):\n",
    "            p += s[i]\n",
    "        for i in range(begin, end):\n",
    "            if s[i] == \"a\":\n",
    "                p += \"z\"\n",
    "            else:\n",
    "                p += chr(ord(s[i])-1)\n",
    "        for i in range(end, len(s)):\n",
    "            p += s[i]\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        #找字符串s中非a的第一个位置为开始，a之前的一个位置为结束\n",
    "        i,left,right,n = 0,-1,-1,len(s)\n",
    "        ans = \"\"\n",
    "        flag = False\n",
    "        while i<n:\n",
    "            if s[i]!='a' and not flag:\n",
    "                left = i\n",
    "                flag = True\n",
    "            if s[i]=='a' and flag:\n",
    "                right = i\n",
    "                break\n",
    "            i+=1\n",
    "        if i==n:\n",
    "            right = i\n",
    "        #表示没有找到替换的起点，也就说s中全是a，那么需要替换最后一个a保证字典序最小\n",
    "        if left==-1:\n",
    "            return s[:n-1]+\"z\"\n",
    "        for idx,c in enumerate(s):\n",
    "            if idx<left or idx>=right:\n",
    "                ans += c\n",
    "            else:\n",
    "                if c!='a':\n",
    "                    ans += chr(ord(c)-1)\n",
    "                else:\n",
    "                    ans += 'z'\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        state = 0\n",
    "        ans = \"\"\n",
    "        for c in s:\n",
    "            if c != \"a\" and not state: state = 1\n",
    "            elif c == \"a\" and state: state = 2\n",
    "            ans += chr((ord(c) - 97 - (state == 1)) % 26 + 97)\n",
    "        return ans if state else ans[:-1] + \"z\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n=len(s)\n",
    "        i=0\n",
    "        while i<n and s[i]=='a':\n",
    "            i+=1\n",
    "        if i==n:\n",
    "            return s[:n-1]+'z'\n",
    "        j=i\n",
    "        while j<n and s[j]!='a':\n",
    "            j+=1\n",
    "        #j-=1\n",
    "        ret=s[:i]\n",
    "        for l in range(i,j):\n",
    "            ret+=chr(ord(s[l])-1)\n",
    "        if j!=n:\n",
    "            ret+=s[j:]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i] == 'a': continue\n",
    "            t = s[:i]\n",
    "            for j in range(i, n):\n",
    "                if s[j] != 'a': t += chr(ord(s[j]) - 1)\n",
    "                else: return t + s[j:]\n",
    "            return t\n",
    "        return s[:-1] + 'z'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        state = 0\n",
    "        ans = \"\"\n",
    "        for c in s:\n",
    "            if c != \"a\":\n",
    "                if not state: state = 1\n",
    "            else:\n",
    "                if state: state = 2\n",
    "            ans += chr((ord(c) - 97 - (state == 1)) % 26 + 97)\n",
    "        return ans if state else ans[:-1] + \"z\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        if set(s) == {'a'}: return s[:len(s)-1] + 'z'\n",
    "        res, flag = '', 0\n",
    "        for i in s:\n",
    "            if flag == 0:\n",
    "                if i=='a': res += 'a'\n",
    "                else: flag = 1\n",
    "            if flag == 1:\n",
    "                if i!='a': res += chr(ord(i)-1)\n",
    "                else: flag = 2\n",
    "            if flag == 2: res += i\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        i = 0\n",
    "        n = len(s)\n",
    "        ret = ''\n",
    "        for i in range(n):\n",
    "            if s[i] == 'a':\n",
    "                continue\n",
    "            ret = 'a' * i\n",
    "            for j in range(i, n):\n",
    "                if s[j] != 'a':\n",
    "                    ret += chr(ord(s[j]) - 1)\n",
    "                else:\n",
    "                    ret += s[j:]\n",
    "                    break\n",
    "            break\n",
    "        if ret == '':\n",
    "            return s[:-1] + 'z'\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        left = 0\n",
    "        right = len(s)\n",
    "        flag = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] != 'a':\n",
    "                left = i\n",
    "                flag = 1\n",
    "                break\n",
    "        if flag == 0:\n",
    "            return s[0:len(s)-1]+'z'\n",
    "        for i in range(left+1,len(s)):\n",
    "            if s[i] == 'a':\n",
    "                right = i\n",
    "                flag = 1\n",
    "                break\n",
    "        change = \"\"\n",
    "        # if flag == 0:\n",
    "        #     return 'z'+s[1:]\n",
    "        for i in range(left,right):\n",
    "            change = change + chr(ord(s[i]) - 1)\n",
    "        print(left,right)\n",
    "        print(change)\n",
    "        print(s[0:left])\n",
    "        print(s[right:])\n",
    "        return s[0:left] + change + s[right:]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        start = 0\n",
    "        while(start < n):\n",
    "            if s[start] != 'a':\n",
    "                break\n",
    "            else:\n",
    "                start += 1\n",
    "        if start == n:\n",
    "            return s[: -1] + 'z'\n",
    "        else:\n",
    "            temp = ''\n",
    "            end = start\n",
    "            while(end < n):\n",
    "                if s[end] != 'a':\n",
    "                    temp += chr(ord(s[end]) - 1)\n",
    "                    end += 1\n",
    "                else:\n",
    "                    break\n",
    "            return s[:start] + temp + s[end:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if s == \"a\" * n:\n",
    "            return \"a\" * (n - 1) + \"z\"\n",
    "\n",
    "        res = \"\"\n",
    "        decreased = False\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if not decreased:\n",
    "                if s[i] == \"a\":\n",
    "                    res += s[i]\n",
    "                else:\n",
    "                    res += chr(ord(s[i]) - 1)\n",
    "                    decreased = True\n",
    "            else:\n",
    "                if s[i] == \"a\":\n",
    "                    break\n",
    "                else:\n",
    "                    res += chr(ord(s[i]) - 1)\n",
    "\n",
    "            i += 1\n",
    "        \n",
    "        res += s[i:]\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        i=0\n",
    "        n=len(s)\n",
    "        while i<n and s[i]=='a':\n",
    "            i+=1\n",
    "        if n==i:\n",
    "            return s[:i-1]+'z'\n",
    "        new_s=s[:i]\n",
    "        while i<n:\n",
    "            if s[i]=='a':\n",
    "                break\n",
    "            else:\n",
    "                new_s+=chr(ord(s[i])-1)\n",
    "            i+=1\n",
    "        new_s+=s[i:]\n",
    "        return new_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if s == 'a' * n:\n",
    "            return s[:-1] + 'z'\n",
    "        cor = False\n",
    "        i = 0\n",
    "        ss = ''\n",
    "        while i < len(s):\n",
    "            if s[i] == 'a':\n",
    "                if cor == True: break\n",
    "                else: ss += s[i]\n",
    "            else:\n",
    "                cor = True\n",
    "                ss += chr(ord(s[i]) - 1)\n",
    "            i += 1\n",
    "        if i < len(s):\n",
    "            ss += s[i:]\n",
    "        return ss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        ans = ''\n",
    "        fir = True\n",
    "        for i in range(n):\n",
    "            if s[i] != 'a':\n",
    "                ans += chr(ord(s[i])-1)\n",
    "                fir = False\n",
    "            elif s[i] == 'a':\n",
    "                if fir:\n",
    "                    ans += s[i]\n",
    "                    continue\n",
    "                else:\n",
    "                    ans += s[i:]\n",
    "                    break\n",
    "        if fir:\n",
    "            ans = ans[:-1]+'z'\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        s_1 = \"\"\n",
    "        flag = False\n",
    "        a_start = True\n",
    "        while len(s) > 0:\n",
    "            if s == \"a\" * len(s) and a_start:\n",
    "                s_1 = \"a\" * (len(s) - 1) + \"z\"\n",
    "                break\n",
    "            elif s[0] == \"a\" and not flag:\n",
    "                s_1 += \"a\"\n",
    "                s = s[1:]\n",
    "                a_start = False\n",
    "            elif s[0] != \"a\":\n",
    "                s_1 += str(chr(ord(s[0]) - 1))\n",
    "                s = s[1:]\n",
    "                flag = True\n",
    "                a_start = False\n",
    "            elif s[0] == \"a\" and flag:\n",
    "                s_1 = s_1 + s\n",
    "                break\n",
    "        return s_1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if s == 'a' * n:\n",
    "            return 'a' * (n - 1) + 'z'\n",
    "        \n",
    "        res = \"\"\n",
    "        f = True\n",
    "        for i in range(n):\n",
    "            if s[i] == 'a' and f:\n",
    "                res += s[i]\n",
    "            elif s[i] == 'a':\n",
    "                res += s[i:]\n",
    "                break\n",
    "            else:\n",
    "                f = False\n",
    "                res += chr(ord(s[i]) - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        pre = -1\n",
    "        index = -1\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'a':\n",
    "                if i - pre <= 1:\n",
    "                    pre = i\n",
    "                else:\n",
    "                    index = i\n",
    "                    break\n",
    "        if index == -1:\n",
    "            if pre == len(s)-1:\n",
    "                return s[:len(s)-1]+'z'\n",
    "            res = ''\n",
    "            for i in range(len(s)):\n",
    "                if i>pre:\n",
    "                    t = chr(ord(s[i])-1)\n",
    "                    res += t\n",
    "                else:\n",
    "                    res += s[i]\n",
    "            return res\n",
    "        else:\n",
    "            res = ''\n",
    "            for i in range(len(s)):\n",
    "                if i>pre and i<index:\n",
    "                    t = chr(ord(s[i])-1)\n",
    "                    res += t\n",
    "                else:\n",
    "                    res += s[i]\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i] == 'a':\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        if i == n:\n",
    "            return s[:n-1]+'z'\n",
    "        else:\n",
    "            j = i\n",
    "            while i < n:\n",
    "                if s[i] != 'a':\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "            k = i\n",
    "            ret = ''\n",
    "            for i in range(n):\n",
    "                if i < j:\n",
    "                    ret += s[i]\n",
    "                elif i < k:\n",
    "                    c = s[i]\n",
    "                    ordc = ord(c)\n",
    "                    ret += chr(ordc - 1)\n",
    "                else:\n",
    "                    ret += s[i]\n",
    "            return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        res = \"\"\n",
    "        index = 0\n",
    "        while(index < len(s) and s[index]=='a'):\n",
    "            res += \"a\"\n",
    "            index += 1\n",
    "\n",
    "        while(index < len(s) and not s[index] == 'a'):\n",
    "            res += chr(ord(s[index]) - 1)\n",
    "            index += 1\n",
    "        if index == len(s):\n",
    "            if res == s:\n",
    "                res = res[:-1] + \"z\"\n",
    "                return res\n",
    "            else:\n",
    "                return res\n",
    "        else:\n",
    "            return res + s[index:]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        ans=''\n",
    "        cnt=0\n",
    "        for i,c in enumerate(s):\n",
    "            if c!='a':\n",
    "                c1=chr(ord(c)-1)\n",
    "                ans+=c1\n",
    "                cnt=1\n",
    "            else:\n",
    "                if cnt:\n",
    "                    ans+=s[i:]\n",
    "                    break\n",
    "                ans+=c\n",
    "        return ans if cnt else ans[:-1]+'z'\n",
    "                \n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        state = 0\n",
    "        ans = \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            if c != \"a\" and not state: state = 1\n",
    "            elif c == \"a\" and state: return ans + s[i:]\n",
    "            ans += chr((ord(c) - 97 - (state == 1)) % 26 + 97)\n",
    "        return ans if state else ans[:-1] + \"z\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        left=0\n",
    "        n=len(s)\n",
    "        while left<n and s[left]=='a':\n",
    "            left+=1\n",
    "        if left==n:\n",
    "            \n",
    "            return s[:-1]+'z'\n",
    "        res=''\n",
    "        right=n\n",
    "        for i in range(n):\n",
    "            if left<=i<right:\n",
    "                if s[i]=='a':\n",
    "                    right=i\n",
    "                    res+='a'\n",
    "                else:\n",
    "                    res+=chr(ord(s[i])-1)\n",
    "            else:\n",
    "                res+=s[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        newS = \"\"\n",
    "        flag = 0\n",
    "        s = 'a'+s\n",
    "        ns = \"\"\n",
    "        \n",
    "        for ss in s:\n",
    "            if ss == 'a' and flag == 0:\n",
    "                ns += ss\n",
    "            elif ss!='a' and (flag == 0 or flag == 1):\n",
    "                flag =1\n",
    "                ns += chr(ord(ss)-1)\n",
    "            elif ss == 'a' and flag==1:\n",
    "                flag=2\n",
    "                ns+=ss\n",
    "            else:\n",
    "                ns+=ss\n",
    "        if flag == 0:\n",
    "            ns= ns[:-1]\n",
    "            ns+='z'\n",
    "        return ns[1:]\n",
    "                \n",
    "                \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        i = 0\n",
    "        res = \"\"\n",
    "        n = len(s)\n",
    "        while i < n and s[i] == 'a':\n",
    "            res += 'a'\n",
    "            i += 1\n",
    "        if i == n:\n",
    "            return res[:-1] + 'z'\n",
    "        while i < n:\n",
    "            if s[i] != \"a\":\n",
    "                res += chr(ord(s[i]) - 1)\n",
    "            else:\n",
    "                break\n",
    "            i += 1\n",
    "        res += s[i:]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        res = ''\n",
    "        edit = False\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == 'a' and edit == True:\n",
    "                res += s[i:]\n",
    "                break\n",
    "            if ch == 'a':\n",
    "                res += ch\n",
    "                continue\n",
    "            res += chr(ord(ch) - 1)\n",
    "            edit = True\n",
    "        if not edit:\n",
    "            return res[:-1] + 'z'\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        idx, l = 0, len(s)\n",
    "        while idx < l and s[idx] == 'a':\n",
    "            idx += 1\n",
    "        if idx == l:\n",
    "            return s[:-1] + 'z'\n",
    "        ans = [s[:idx]]\n",
    "        while idx < l and s[idx] != 'a':\n",
    "            ans.append(chr(ord(s[idx])-1))\n",
    "            idx += 1\n",
    "        ans.append(s[idx:])\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        i, j = -1, -1\n",
    "        for k in range(n):\n",
    "            if s[k] == 'a':\n",
    "                continue\n",
    "            else:\n",
    "                i = k\n",
    "                while k < n and s[k] != 'a':\n",
    "                    k += 1\n",
    "                j = k\n",
    "                break\n",
    "            \n",
    "        \n",
    "        def mv(s):\n",
    "            return ''.join([chr((ord(c) - ord('a') + 25) % 26 + ord('a')) for c in s])\n",
    "        \n",
    "        # 找到了第一段非a子串:\n",
    "        if i != -1 and j != -1:\n",
    "            return s[: i] + mv(s[i: j]) + s[j:]\n",
    "        else: #全是a的子串\n",
    "            return s[: -1] + 'z'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        left = 0\n",
    "        while left < len(s) and s[left] == 'a':\n",
    "            left += 1\n",
    "        \n",
    "        if left == len(s):\n",
    "            return s[:len(s) - 1] + 'z'\n",
    "        \n",
    "        right = left + 1\n",
    "        while right < len(s) and s[right] != 'a':\n",
    "            right += 1\n",
    "        \n",
    "        return s[:left] + ''.join([chr(ord(ch) - 1) for ch in s[left : right]]) + s[right:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n=len(s)\n",
    "        i=0\n",
    "        while i<n and s[i]=='a':\n",
    "            i+=1\n",
    "        if i==n:\n",
    "            return s[:-1]+'z'\n",
    "        s=list(s)\n",
    "        while i<n and s[i]!='a':\n",
    "            s[i]=chr(ord(s[i])-1)\n",
    "            i+=1\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        # 选择第一个非a字符子字符串，翻转\n",
    "        # 找到第一个非a字符，如果全是a，返回-1\n",
    "        first = next((i for i, c in enumerate(s) if c != 'a'), -1)\n",
    "        if first == -1:\n",
    "            return s[:-1] + 'z'\n",
    "        s = list(s)\n",
    "        for i in range(first, len(s)):\n",
    "            if s[i] == 'a':\n",
    "                break\n",
    "            s[i] = chr(ord(s[i]) - 1)\n",
    "        return ''.join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        l,n,s = 0,len(s),list(s)\n",
    "        while l < n and s[l] == 'a': l += 1\n",
    "        if l == n: return 'a' * (n - 1) + 'z'\n",
    "        while l < n and s[l] != 'a':\n",
    "            s[l] = chr(ord(s[l]) - 1)\n",
    "            l += 1\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        slist = list(s)\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if(slist[i] != 'a'):\n",
    "                j = i \n",
    "                while(j < n and slist[j] != 'a'):\n",
    "                    slist[j] = chr(ord(slist[j])-1)\n",
    "                    j += 1\n",
    "                return ''.join(slist)\n",
    "        slist[-1] = 'z'\n",
    "        return ''.join(slist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        op = False\n",
    "        for i, c in enumerate(s):\n",
    "            if s[i] == 'a':\n",
    "                if not op:\n",
    "                    continue\n",
    "                else:\n",
    "                    break\n",
    "            s[i] = chr(ord(c) - 1)\n",
    "            op = True\n",
    "        if not op:\n",
    "            s[-1] = 'z'\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        slist = list(s)\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if(slist[i] != 'a'):\n",
    "                j = i \n",
    "                while(j < n and slist[j] != 'a'):\n",
    "                    slist[j] = chr(ord(slist[j])-1)\n",
    "                    j += 1\n",
    "                return ''.join(slist)\n",
    "        slist[-1] = 'z'\n",
    "        return ''.join(slist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != \"a\":\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == \"a\":\n",
    "                        break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return \"\".join(t)\n",
    "        t[-1] = \"z\"\n",
    "        return \"\".join(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i] == 'a':\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        if i == n:\n",
    "            return s[:n-1]+'z'\n",
    "        else:\n",
    "            j = i\n",
    "            while i < n:\n",
    "                if s[i] != 'a':\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "            k = i\n",
    "            ret = []\n",
    "            for i in range(n):\n",
    "                if i < j or i >= k:\n",
    "                    ret.append(s[i])\n",
    "                elif i < k:\n",
    "                    c = s[i]\n",
    "                    ordc = ord(c)\n",
    "                    ret.append(chr(ordc - 1))\n",
    "            return ''.join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        change = {'a': 'z', 'b': 'a', 'c': 'b', 'd': 'c', 'e': 'd', 'f': 'e', 'g': 'f', 'h': 'g', 'i': 'h', 'j': 'i', 'k': 'j', 'l': 'k', 'm': 'l', 'n': 'm', 'o': 'n', 'p': 'o', 'q': 'p', 'r': 'q', 's': 'r', 't': 's', 'u': 't', 'v': 'u', 'w': 'v', 'x': 'w', 'y': 'x', 'z': 'y'}\n",
    "        left = None\n",
    "        for i in range(len(s)):\n",
    "            if s[i] != 'a':\n",
    "                left = i\n",
    "                break\n",
    "        if left is None:\n",
    "            temp = list(s)\n",
    "            temp[-1] = 'z'\n",
    "            return ''.join(temp)\n",
    "        temp = list(s)\n",
    "        for i in range(left, len(s)):\n",
    "            if s[i] != 'a':\n",
    "                continue\n",
    "            else:\n",
    "                for j in range(left, i):\n",
    "                    temp[j] = change[temp[j]]\n",
    "                return ''.join(temp)\n",
    "        for j in range(left, len(temp)):\n",
    "            temp[j] = change[temp[j]]\n",
    "        return ''.join(temp)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        slist = list(s)\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if(slist[i] != 'a'):\n",
    "                j = i \n",
    "                while(j < n and slist[j] != 'a'):\n",
    "                    slist[j] = chr(ord(slist[j])-1)\n",
    "                    j += 1\n",
    "                return ''.join(slist)\n",
    "        slist[-1] = 'z'\n",
    "        return ''.join(slist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if s == 'a' * n:\n",
    "            return 'a' * (n - 1) + 'z'\n",
    "        l = []\n",
    "        f = 0\n",
    "        for c in s:\n",
    "            if f == 2:\n",
    "                l.append(c)\n",
    "            elif f == 1:\n",
    "                if c == 'a':\n",
    "                    f = 2\n",
    "                    l.append(c)\n",
    "                else:\n",
    "                    l.append(chr(ord(c) - 1))\n",
    "            else:\n",
    "                if c == 'a':\n",
    "                    l.append(c)\n",
    "                else:\n",
    "                    f = 1\n",
    "                    l.append(chr(ord(c) - 1))\n",
    "        return ''.join(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        # 选择第一个非a字符子字符串，翻转\n",
    "        # 找到第一个非a字符，如果全是a，返回-1\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i,c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i,len(t)):\n",
    "                    if t[j] == 'a':break\n",
    "                    t[j] = chr(ord(t[j])-1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        # 改的越高位越好, 但是遇到a就得停下,后面的其实改不改都行\n",
    "        # 长度为1时必须要改, 所以要写特例\n",
    "        if len(s) == 1:\n",
    "            if s == 'a':\n",
    "                return 'z'\n",
    "            else:\n",
    "                return chr(ord(s) - 1)\n",
    "\n",
    "        ret = []\n",
    "        curLeft = 0\n",
    "        while curLeft < len(s) and s[curLeft] == 'a':\n",
    "            ret.append(s[curLeft])\n",
    "            curLeft += 1\n",
    "\n",
    "        if curLeft == len(s):\n",
    "            ret[-1] = 'z'\n",
    "            return ''.join(ret)\n",
    "            \n",
    "        curRight = curLeft\n",
    "        while curRight < len(s) and s[curRight] != 'a':\n",
    "            ret.append(chr(ord(s[curRight]) - 1))\n",
    "            curRight += 1\n",
    "        while curRight < len(s):\n",
    "            ret.append(s[curRight])\n",
    "            curRight += 1\n",
    "        return ''.join(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "      res=[]\n",
    "      isc=True\n",
    "      for i,t in enumerate(s):\n",
    "        if t!='a':\n",
    "          res.append(chr(ord(t)-1))\n",
    "          isc=False\n",
    "        elif isc:\n",
    "          res.append('a')\n",
    "        else:\n",
    "          return \"\".join(res)+s[i:]\n",
    "      if isc:res[-1]='z'\n",
    "      return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        i = 0\n",
    "        for a in t:\n",
    "            if a != 'a':\n",
    "                while i < len(t) and t[i] != 'a':\n",
    "                    t[i] = chr(ord(t[i]) - 1)\n",
    "                    i += 1\n",
    "                return \"\".join(t)\n",
    "            i += 1\n",
    "        t[-1] = 'z'\n",
    "        return \"\".join(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        l = list(s)\n",
    "        for i, c in enumerate(s):\n",
    "            if c != 'a':\n",
    "                for j in range(i,n):\n",
    "                    if l[j] == 'a':\n",
    "                        break\n",
    "                    l[j] = chr(ord(l[j]) - 1)\n",
    "                return \"\".join(l)\n",
    "        l[-1] = 'z'\n",
    "        return \"\".join(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        n = len(t)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, n):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return ''.join(t)\n",
    "        t[n - 1] = 'z'\n",
    "        return ''.join(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def smallestString(self, s: str) -> str:\r\n",
    "        n = len(s)\r\n",
    "        t = list(s)\r\n",
    "        for i in range(n):\r\n",
    "            if s[i] != 'a':\r\n",
    "                for j in range(i, n):\r\n",
    "                    if s[j] == 'a':\r\n",
    "                        break\r\n",
    "                    else:\r\n",
    "                        t[j] = chr(ord(s[j]) - 1)\r\n",
    "                return ''.join(t)\r\n",
    "        #全是a,最后一个变成z\r\n",
    "        t[-1] = 'z'\r\n",
    "        return ''.join(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        s1 = list(s)\n",
    "        for i, k in enumerate(s1):\n",
    "            if k != 'a':\n",
    "                for j in range(i, len(s1)):\n",
    "                    if s1[j] == 'a':\n",
    "                        break\n",
    "                    s1[j] = chr(ord(s1[j]) - 1)\n",
    "                return ''.join(s1)\n",
    "        s1[-1] = 'z'\n",
    "        return ''.join(s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i,c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i,len(t)):\n",
    "                    if t[j] == 'a':\n",
    "                        break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        # 选择第一个非a字符子字符串，翻转\n",
    "        # 找到第一个非a字符，如果全是a，返回-1\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        if n == 1:\n",
    "            return str(chr((ord(s[0]) - 72) % 26 + 97))\n",
    "        \n",
    "        start_index = -1\n",
    "        end_index = n - 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            if s[i] == 'a':\n",
    "                continue\n",
    "            else:\n",
    "                start_index = i\n",
    "                break\n",
    "        \n",
    "        if start_index == -1:\n",
    "            return 'a' * (n - 1) + 'z'\n",
    "        \n",
    "        for j in range(i + 1, n):\n",
    "            if s[j] == 'a':\n",
    "                end_index = j - 1\n",
    "                break\n",
    "                \n",
    "        # print(start_index, end_index)\n",
    "        ret = [x for x in s]\n",
    "        for i in range(start_index, end_index+1):\n",
    "            ret[i] = str(chr((ord(s[i]) - 72) % 26 + 97))\n",
    "        \n",
    "        return ''.join(ret)\n",
    "        \n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i] != \"a\":\n",
    "                start = i\n",
    "                for j in range(i+1,n):\n",
    "                    if s[j] == \"a\":\n",
    "                        end = j-1\n",
    "                        break\n",
    "                else:\n",
    "                    end = n-1\n",
    "                break\n",
    "        else:\n",
    "            return s[:n-1]+\"z\" \n",
    "        ls = []\n",
    "        for i in range(start):\n",
    "            ls.append(s[i])\n",
    "        for i in range(start,end+1):\n",
    "            ls.append(chr(ord(s[i])-1))\n",
    "        for i in range(end+1,n):\n",
    "            ls.append(s[i])\n",
    "        return \"\".join(ls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        list1 = list(s)\n",
    "        for i in range(len(list1)):\n",
    "            if list1[i] != 'a':\n",
    "                for j in range(i,len(list1)):\n",
    "                    if list1[j] != 'a':\n",
    "                        list1[j] = chr(ord(list1[j])-1)\n",
    "                    else:\n",
    "                        break\n",
    "                return ''.join(list1)\n",
    "        list1[-1] = 'z'\n",
    "        return ''.join(list1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        n=len(s)\n",
    "        l=0\n",
    "        q=list(s)\n",
    "        if max(s)=='a':\n",
    "            return s[:-1]+'z'\n",
    "        while l<n and s[l]=='a':\n",
    "            l+=1\n",
    "        r=l\n",
    "        while r<n and s[r]!='a':\n",
    "            q[r]=chr(ord(s[r])-1)\n",
    "            r+=1\n",
    "        return ''.join(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        i = 0\n",
    "        t = list(s)\n",
    "        while i < len(t):\n",
    "            if t[i]=='a':\n",
    "                i+=1\n",
    "            else:\n",
    "                break\n",
    "        j = i\n",
    "        while j < len(s):\n",
    "            if t[j]!='a':\n",
    "                j+=1\n",
    "            else:\n",
    "                break\n",
    "        if i == len(s):\n",
    "            t[-1] = 'z'\n",
    "        else:\n",
    "            for k in range(i,j):\n",
    "                t[k] = chr(ord(t[k])-1)\n",
    "        return \"\".join(t)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        s = list(s)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] != 'a':\n",
    "                for j in range(i, len(s)):\n",
    "                    if s[j] == 'a': break\n",
    "                    s[j] = chr(ord(s[j])-1)\n",
    "                return ''.join(s)\n",
    "           \n",
    "        s[-1] = 'z'\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j])-1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 贪心\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a':\n",
    "                        break\n",
    "\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "\n",
    "                return ''.join(t)\n",
    "\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j])-1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, c in enumerate(t):\n",
    "            if c != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return ''.join(t)\n",
    "        t[-1] = 'z'\n",
    "        return ''.join(t)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        t = list(s)\n",
    "        for i, value in enumerate(t):\n",
    "            if value != 'a':\n",
    "                for j in range(i, len(t)):\n",
    "                    if t[j] == 'a': break  # 因为如果子字符串里面包含a的话会增大字典序\n",
    "                    t[j] = chr(ord(t[j]) - 1)\n",
    "                return \"\".join(t)  \n",
    "        t[-1] = 'z'  \n",
    "        # 因为如果上面条件未执行证明字符串全为a 因题目要求必须选择字符串 所以将最后一个字符改为z\n",
    "        return \"\".join(t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        index = 0\n",
    "        n = len(s)\n",
    "        \n",
    "        while index < n and s[index] == 'a':\n",
    "            ans.append(\"a\")\n",
    "            index += 1\n",
    "            \n",
    "        if index == n:\n",
    "            return s[:n - 1] + \"z\"\n",
    "            \n",
    "        while index < n and s[index] != 'a':\n",
    "            ans.append(chr(ord(s[index]) - 1))\n",
    "            index += 1\n",
    "        \n",
    "        return \"\".join(ans) + s[index:]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s):\n",
    "        chars = list(s)\n",
    "\n",
    "        # 遍历字符列表\n",
    "        for i in range(len(chars)):\n",
    "            # 如果当前字符不是 'a'，则可以替换为前一个字符\n",
    "            if chars[i] != 'a':\n",
    "                # 从当前位置开始，将字符替换为前一个字符，直到遇到 'a'\n",
    "                for j in range(i, len(chars)):\n",
    "                    if chars[j] == 'a':\n",
    "                        break  # 遇到 'a' 停止替换\n",
    "                    chars[j] = chr(ord(chars[j]) - 1)\n",
    "                break  # 只执行一次替换操作\n",
    "        else:\n",
    "            # 如果字符串全部是 'a'，则将最后一个 'a' 替换为 'z'\n",
    "            chars[-1] = 'z'\n",
    "\n",
    "        # 将字符列表转换回字符串并返回\n",
    "        return ''.join(chars)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestString(self, s: str) -> str:\n",
    "        a = s.split('a')\n",
    "        for i in range(len(a)):\n",
    "            if a[i]:\n",
    "                b = ''\n",
    "                for j in a[i]:\n",
    "                    b += chr(ord(j) - 1)\n",
    "                s = s.replace(a[i],b,1)\n",
    "                return s\n",
    "        s = s[:len(s)-1]\n",
    "        s += 'z'\n",
    "        return s"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
